#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <stdbool.h>

using namespace std;

namespace matrix
{
    template<class V,class W,bool G=false>
    class Graph
    {
        private:
            vector<V> _vertexs;
            map<V,int> _indexMap;
            vector<vector<W>> _matrix;

        public:
            Graph(const V* arr,size_t n)
            {
                _vertexs.reserve(n);

                for(size_t i=0;i<n;i++)
                {
                    _vertexs[i]=arr[i];
                    _indexMap[arr[i]]=i;
                }

                _matrix.resize(n);

                for(size_t i=0;i<n;i++)
                {
                    _matrix[i].resize(n,INT32_MAX);
                }
            }


           size_t GetVertexIndex(const V& v)
           {
               auto it=_indexMap.find(v);
               if(it!=_indexMap.end())
               {
                   return it.second;
               }
               else 
               {
                   perror("_indexMap.find()");
                   return -1;
               }
           }

            void AddEdge(const V& src,const V& dst,const W& w)
            {
                size_t srci=GetVertexIndex(src);
                size_t dsti=GetVertexIndex(dst);

                _matrix[srci][dsti]=w;
                if(G==false)
                {
                    _matrix[dsti][srci]=w;
                }

            }
            
            void Print()
            {
                for(int i=0;i<_vertexs.size();i++)
                {
                    cout<<_vertexs[i]<<endl;
                }

                

                

            }

    };

    void TestGraph()
    {
        int arr[]={1,3,5,7,9};

        Graph<int,int> g(arr,5);

        g.Print();
    }
};

namespace linkTable
{

    template<class W>
    struct Edge 
    {
        int _dst;
        Edge<W>* _next;
        W _w;

        Edge(int dst,const W& w)
            :_dst(dst)
            ,_next(nullptr)
            ,_w(w)
        {

        }
    };

    template<class V,class W,bool G>
    class Graph 
    {
        typedef Edge<W> Edge;

      private:
          vector<V> _vertexs;
          map<V,int> _indexMap;
          vector<Edge*> _table;

    public:
          Graph(const V* arr,size_t n)
          {
              _vertexs.reserve(n);
              for(int i=0;i<n;i++)
              {
                  _vertexs[i]=arr[i];
                  _indexMap[arr[i]]=i;
              }

              _table.resize(n,nullptr);
          }


        size_t GetIndex(const V& v)
        {
            auto it=_indexMap.find(v);
            if(it!=_indexMap.end())
            {
                return it.second;
            }
            else 
            {
                return -1;
            }
        }

          void AddEdge(const V& src,const V& dst,const W& w)
          {
              size_t srci=GetIndex(src);
              size_t dsti=GetIndex(dst);

              Edge* newEdge=new Edge(dsti,w);
              newEdge->_next=_vertexs[srci];
              _vertexs[srci]=newEdge;
              if(G==false)
              {
                Edge* newEdge=new Edge(srci,w);
                newEdge->_next=_vertexs[dsti];
                _vertexs[dsti]=newEdge;

              }
          }

    };
};






